Матч 399, Танцы на вечеринке (DancingParty)

Дивизион 1, Уровень 3

На вечеринку приглашены n мальчиков и n девочек. Они хотят танцевать несколько раундов. В каждом раунде гости делятся на n танцующих пар. Каждый гость должен быть в некоторой паре, каждая пара должна состоять из одного мальчика и одной девочки. В каждом раунде каждый мальчик должен танцевать с другой девочкой. Некоторые мальчики и девочки не нравятся друг другу. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Аналогично каждая девочка может танцевать не более чем с k мальчиками, которые ей не нравятся.

Массив likes описывает отношения между мальчиками и девочками: likes[i][j] = ‘Y’, если i - ому мальчику нравится j - ая девочка. Иначе likes[i][j] = ‘N’. Какое наибольшее количество раундов мальчики и девочки смогут танцевать?

Класс: DancingParty

Метод: int maxDances(vector<string> likes, int k)

Ограничения: likes содержит от 1 до 50 элементов, likes[i] содержит n символов ‘Y’ и ‘N’ (n - количество строк в likes), 0 ≤ k ≤ 50.

Вход. Массив likes, описывающий отношения между гостями и целое число k.

Выход. Наибольшее количество раундов, которое мальчики и девочки смогут танцевать.

Пример входа

likes	k
{"YYY", "YYY", "YYY"}	0
{"YYY", "YYN", "YNY"}	0
{"YN", "YN"}	1

Пример выхода

3

2

1

РЕШЕНИЕ

максимальный поток

Рассмотрим следующую задачу: могут ли танцы продолжаться в точности m раундов? Если мы сможем ответить на этот вопрос, то бинарным поиском найдем наибольшее m, для которого проведение танцев возможно.

Построим граф, имеющий один исток и один сток (черные вершины). Красные вершины представляют мальчиков, серые – девочек. Если мальчик и девочка нравятся друг другу, то проведем между ними ребро единичной пропускной способности (на рисунке такими являются два ребра – верхнее и нижнее). Иначе добавим синие и зеленые вершины как показано на рисунке и установим пропускную способность ребер между соответствующими синими и зелеными вершинами равную 1.

Синие и зеленые вершины образуют “защитный” уровень. Связь мальчиков с девочками, которые друг другу не нравятся, будет проходить по ребрам защитного уровня. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Установим пропускную способность ребер между красными и синими, зелеными и серыми вершинами равную k. Таким образом, между каждым мальчиком и каждой девочкой будет установлена связь через ребро либо напрямую, либо через вершины защитного уровня.

Танцы должны продолжаться в точности m раундов. Установим пропускную способность ребер между истоком и красными вершинами, а также между серыми вершинами и стоком равную m.

Находим максимальный поток в графе. Танцы могут продолжаться в точности m раундов тогда и только тогда, когда величина максимального потока будет равна n * m, где n – количество мальчиков.

При построении матрицы пропускных способностей g вершины графа имеют следующие номера:

· исток: номер 0;

· красные вершины: от 1 до n;

· синие вершины: от n + 1 до 2*n;

· синие вершины: от 2*n + 1 до 3*n;

· синие вершины: от 3*n + 1 до 4*n;

· сток: номер 4*n + 1;

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <memory>

using namespace std;

#define MAX 52

int g[4*MAX][4*MAX],used[4*MAX];

int n,flow,MaxFlow;

int aug(int x,int t,int CurFlow)

{

if (x == t) return CurFlow;

if (used[x]++) return 0;

for (int Flow,y = 0; y <= 4*n+1; y++)

{

if (g[x][y] > 0 && (Flow = aug(y,t,min(CurFlow,g[x][y]))))

{

g[x][y] -= Flow; g[y][x] += Flow;

return Flow;

}

}

return 0;

}

int CanDance(int m,int k,vector<string> &likes)

{

int i,j;

for(i=1;i<=n;i++) g[0][i] = g[3*n+i][4*n+1] = m;

for(i=1;i<=n;i++) g[i][n+i] = g[2*n+i][3*n+i] = k;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if (likes[i][j] == 'Y') g[i+1][3*n+j+1] = 1; else g[n+i+1][2*n+j+1] = 1;

MaxFlow = 0;

do

{

memset(used,0,sizeof(used));

} while ((flow = aug(0,4*n+1,0x7FFFFFFF)) && (MaxFlow += flow));

return MaxFlow == m*n;

}

class DancingParty

{

public:

int maxDances(vector<string> likes, int k)

{

int m,low=0,high;

high=n=(int)likes.size();

memset(g,0,sizeof(g));

while(low<high)

{

m = (low+high+1)/2;

if(CanDance(m,k,likes)) low = m; else high = m-1;

}

return low;

}

};